\magnification = \magstep1

\font\titlefont=cmbx10 scaled \magstep3 
\font\sectionfont=cmr10 scaled \magstep2
\font\magone=cmr10 scaled \magstep1
\font\magonebf=cmbx10 scaled \magstep1 
\font\bigone=cmr10 scaled \magstep1
\font\bigtwo=cmr10 scaled \magstep2
\font\bigthree=cmr10 scaled \magstep3
\font\bigfour=cmr10 scaled \magstep4

\def\boxit#1{\vbox{\hrule\hbox{\vrule\kern3pt\vbox{#1}\kern3pt\vrule}\hrule}}

\def\CC{C\raise.08ex\hbox{\tt ++\ }}
\def\CCC{C\raise.08ex\hbox{\tt ++}}
\def\gg{g\hbox{\tt ++\ }}
\def\nat{\hbox{\rm\vrule\kern-0.045em N}}
\def\real{\hbox{\rm\vrule\kern-0.035em R}}
\def\nl{\hfill\break}
\def\'{^\prime}
\def\beginitem   {\parindent 20pt }
\def\enditem     {\parindent 0pt }
\def\refstart #1 {\parindent #1 }
\def\refend      {\parindent 0pt }
\def\ref #1 #2   {\item {\hbox to \parindent {\bf \ [#1] \hfill}} #2}


\def\op  #1 #2 #3 #4 {& $#1$ & \var.#2($#3$)   & #4\cr}
\def\nop #1          {&      &                 & #1\cr}
\def\decl #1 #2 
{{\bf declare}($#1, #2$) \def\type {#1} \def\name {$#1(#2)$} }
\def\decltwo #1 #2 #3 
{{\bf declare2}($#1, #2, #3$) \def\type {#1} \def\name {$#1(#2,#3)$} }
\def\declthree #1 #2 #3 #4
{{\bf declare2}($#1, #2, #3, #4$) \def\type {#1} \def\name {$#1(#2,#3,#4)$} }
\def\create #1 #2 { \name\ \ $#1 #2$; \def\var {$#1$} }
\def\operations  {Operations on a \type\ \var}
\def\precond {{\it Precondition}: }
\def\n {$\backslash$n}

\def\boxit#1{\vbox{\hrule\hbox{\vrule\kern3pt\vbox{#1}\kern3pt\vrule}\hrule}}

\def\WHILE {{\bf while}\ }
\def\IF {{\bf if}\ }
\def\ELSE {{\bf else\ }}



\hsize=17 truecm
\vsize=24.5 truecm

\hoffset=1.5truecm
\voffset=1.6truecm

\parindent 0pt
\parskip 8pt plus 1pt minus 1pt 



\vglue 1truecm
\centerline{{\magonebf LEDA}}
\vglue .5truecm
\centerline{{\magonebf A Library of Efficient Data Types and Algorithms}
\footnote{*}
{This research was supported by the ESPRIT II Basic Research Action Program, 
ESPRIT \ P. 3075 -- ALCOM. Most of this work was carried out while the authors
were affiliated with Fachbereich Informatik, Universit\"at des Saarlandes.}}
\vglue 1truecm
\centerline{Kurt Mehlhorn and Stefan N\"aher}
\vglue .5truecm
\centerline{Max-Planck-Institut f\"ur Informatik}
\centerline{D-6600 Saarbr\"ucken, Federal Republic of Germany}
\vglue 1truecm 
{\bf Key words}: abstract data type, reusable software, efficient algorithms,
object oriented programming
\vglue 1truecm 
\centerline{\bf Abstract}
{\parindent 1.5truecm
{\narrower\smallskip\noindent
LEDA is a library of efficient data types and algorithms.
At present, its strength is graph algorithms and related data
structures. The computational geometry part is evolving.
The main features of the library are 
\smallskip\noindent
-- a sizable collection of data types and algorithms,\nl
-- the precise and readable specification of these types,\nl
-- the inclusion of many of the most recent and efficient implementations,\nl
-- a comfortable data type graph,\nl
-- its extendibility, and\nl
-- its ease of use.
\smallskip}}


\bigskip
{\magonebf I. Introduction}

There is no standard library of the data structures and
algorithms of combinatorial computing.
This is in sharp contrast to many other areas of computing.
There are, e.g., packages in statistics (SPSS), numerical
analysis (LINPACK, EISPACK), symbolic computation
(MACSYMA, SAC-2) and linear programming (MPSX).

In fact the situation is worse, since even within small groups,
say the algorithms group at
our home institution, software frequently is not shared.
Rather, each researcher starts from scratch and, e.g., develops
his own version of a balanced tree.
Of course, this continuous ``reimplementation of the wheel'' slows
down progress, within research and even more so
outside.
This is due to the fact that outside research the investment
for implementing an efficient solution frequently is not made,
because it is doubtful whether the implementation can be reused,
and therefore methods which are known to be less efficient are
used instead.
Thus the scientific discoveries migrate only slowly into
practice.

One of the major differences between combinatorial computing
and other areas of computing such as statistics, numerical
analysis and linear programming is the use
of complex data types.
Whilst the built-in types, such as integers, reals, vectors, and matrices,
usually suffice in the other areas, combinatorial 
computing relies heavily on types like stacks, queues, dictionaries,
sequences, sorted sequences, priority queues, graphs, points,
planes, $\ldots$



In 1989, we started a project (called LEDA, for Library of
Efficient Data types and Algorithms) to build a library of
the data types and algorithms of combinatorial computing. The
features of LEDA are:

\beginitem
\item{$\bullet$} 
LEDA provides a sizable collection of 
data types and algorithms in a form which allows them to be
used by non-experts. In the first version of LEDA, which has
been completed in the spring of 1990, this collection 
included most of the data types and algorithms described in
the text books of the area(e.g. [AHU83],[M84],[T83],[CLR90]),
i.e., stacks, queues, lists, sets, dictionaries, ordered
sequences, partitions, priority queues, directed, undirected, and
planar graphs, lines, points, planes and basic algorithms 
in graph and network theory and
computational geometry. We refer the reader to the LEDA manual([N90]) 
for the list of data types and algorithms available as of Fall 1990. 

\item {$\bullet$}
LEDA gives a precise and readable specification
for each of the data types and algorithms mentioned above.
The specifications are short (typically, not more than a page),
general (so as to allow several implementations), and abstract (so
as to hide all details of the implementation). 
For many efficient data structures access by position is important. 
In LEDA, we use an item concept to cast positions into an abstract 
form. We introduce this concept in section II and demonstrate 
its usefulness on several examples. We mention that most of 
the specifications given in the LEDA manual use this concept, 
i.e., the concept is adequate for the description of many data types.

\item {$\bullet$}
LEDA contains efficient implementations for each of the
data types, e.g., Fibonacci heaps and redistributive heaps for
priority queues, red-black trees and dynamic perfect hashing for
dictionaries, ...

\item {$\bullet$}
LEDA contains a comfortable data type graph. 
It offers the standard iterations such as ``for all nodes $v$
of a graph $G$ do'' (written $forall\_nodes(v,G)$) or ``for all
neighbors $w$ of $v$ do'' (written $forall\_adj\_nodes(w,v)$), it
allows to add and delete vertices and edges and it offers
arrays and matrices indexed by nodes and edges,..., cf. section~III 
for details. The data type graph allows to write programs for graph problems
in a form close to the typical text book presentation. We emphasize
that all examples given in this paper show executable code. 
A long term goal
is the equation ``Algorithm + LEDA = program''.

\enditem

In this paper we describe the status of the project.
We hope that LEDA will narrow
the gap between algorithms research, teaching, and
implementation. Other projects with similar goals are described
in ([B87],[Lin89],[So89]); however, all of these projects settle for a
considerably smaller collection of data types and algorithms than
LEDA.
Our approach to reach the goals of LEDA is standard. Similarly
to the other projects we employ

\beginitem
\item{1.} a strict separation between abstract data types and the 
concrete data structures used to implement them,
\item{2.} parameterized data types, and 
\item{3.} object oriented programming.
\enditem


The implementation language of LEDA is \CC. We have chosen \CC
because of its flexibility and availability. All data types
and algorithms are precompiled modules which can be linked
with application programs. Polymorphic types are implemented
as described in ([St86]).

This paper is organized as follows.
In section II we discuss data types and data structures, and in
section III the data type graph and the interaction of graphs 
and other data types.  In section IV we briefly comment on the 
extendibility and in section V on the internal structure of LEDA. 
Section VI gives a short summary.

The design of LEDA is joint work by the two authors, the implementation
was mostly done by the second author. The library can be used under UNIX
with the \CC compilers AT\&T cfront 2.0, cfront 2.1 and GNU \gg (version 1.37). It is available from the authors for a handling charge of DM 100.


\bigskip
\bigskip
{\magonebf II. Data Types and Items}

In this section we discuss the specification of data types in 
LEDA on the basis of three examples: dictionaries, priority
queues, and partitions. 


\bigskip
{\magone Example 1: Dictionaries}

A popular specification of dictionaries defines a 
dictionary as a partial function from some type $K$ to 
some other type $I$, or alternatively, as a
set of pairs from $K\times I$, i.e., as the graph of 
the function. In an implementation each pair $(k,i)$ 
in the dictionary is stored in some location
of the memory. Efficiency dictates that the pair $(k,i)$ cannot only be
accessed through the key $k$ but also through the location where it
is stored, e.g., we might want to lookup the information $i$ associated 
with key $k$ (this involves a search in the data structure), then compute 
with the value $i$ a new value $i\'$, and finally associate the new value 
with $k$.  This either involves another search in the data structure or, if 
the lookup returned the location where the pair $(k,i)$ is stored, can be 
done by direct access. Of course, the second solution is more efficient and 
we therefore wanted to provide it in LEDA.

In LEDA, the abstraction of a position or location is called an item. 
An item is a container which can hold an object relevant for the data 
type. In the case of dictionaries a $dic\_item$ contains a pair consisting 
of a key and an information.  
An object of type $dictionary(K,I)$, where $K$ and $I$ are types, is 
thus defined as a collection of items (of type $dic\_item$) where each item 
contains a pair in $K\times I$. We use $<k,i>$ to denote an item with key 
$k$ and information $i$ and require that for each $k\in K$ there is at most 
one $i\in I$ such that $<k,i>$ is in the dictionary. 
In mathematical terms this definition may be rephrased as follows: 
A dictionary $D$ is a partial function from the set $dic\_item$ to the 
set $K\times I$. Moreover, for each $k\in K$ there is at most one $i\in I$ 
such that the pair $(k,i)$ is in the range of $D$.

The semantics of the operations 
\smallskip
\+\quad\quad &$dic\_item$ &$D$.lookup($K\ k$)\cr
\+           &$I$         &$D$.inf($dic\_item\ it$)\cr
\+           &$void$      &$D$.change\_inf($dic\_item\ it,\ I\ i\'$)\cr
is now as follows:
$D$.lookup($k$) takes a key $k$ and returns the item $it$ with contents 
$(k,i)$ (it returns $nil$ if there is no such item), $D$.inf($it$) extracts 
$i$ from $it$, and a new value $i\'$ can be associated with $k$ by 
$D$.change\_inf($it,i\'$).


Let us have a look at the insert operation for dictionaries next:

\+&$dic\_item$ &$D$.insert($K\ k,\ I\ i$)\cr

There are two cases to consider. If $D$ contains an item $it$ with contents
$(k,i\')$ then $i\'$ is replaced by $i$ and $it$ is returned. If $D$ contains
no such item, then a new item, i.e., an item which is not contained in any 
dictionary, is added to $D$, this item is made to contain $(k,i)$ and is
returned. 

{\bf Remarks}: 
\beginitem

\item {1.}
In LEDA specifications we use 
\ ``$T_0$ \quad XYZ.$op(T_1\ t_1,\ \dots,\ T_k\ t_k)$''\ 
to denote an operation $op$ applied to an object XYZ with result type $T_0$ 
and arguments $t_1,\dots,\ t_k$ of types $T_1,\dots,\ T_k$ respectively.

\item {2.}
Some readers may find it useful to interpret a $dic\_item$ as
a pointer to a variable of type $K\times I$. The difference is that the
assignment to the variable contained in a $dic\_item$ is restricted, e.g., the
$K$-component cannot be changed, and that in return for this restriction the
access to $dic\_items$ is more flexible than for ordinary variables, e.g.,
access through the value of the $K$-component is possible.

\enditem

Dictionaries are implemented by leaf-oriented red-black trees.
Operations insert and lookup take time $O(\log n)$, key, inf, and change\_inf 
take time $O(1)$. Here $n$ is the current size of the dictionary. 
The space requirement is $O(n)$.
 

We next give a simple application of the dictionary data type.
Program 1 reads a sequence of strings terminated by ``stop'' and counts the 
number of occurrences of each string in the sequence.
The number of occurrences is then listed for each string in the
sequence.
\bigskip
\cleartabs
\+\ (1)\ \ &{\bf declare2}(dictionary, string, int)\cr
\smallskip
\+\ (2) &{\bf main}()\cr
\+\ (3) &$\{$\ \ &\cr
\+\ (4) &  &dictionary(string, int) $D$;\cr
\smallskip
\+\ (5) &  &string $s$;\cr
\+\ (6) &  &dic\_item $it$;\cr
\smallskip
\+\ (7) &  &{\bf while} &( (cin $>> s$) \&\& ($s$ != ``stop'') )\cr
\+\ (8) &  &\ \  &$\{$ &$it = D$.lookup($s$);\cr
\+\ (9) &  &     &    &\IF ($it==nil$) $D$.insert($s,1$);\cr
\+(10) &  &     &    &\ELSE $D$.change\_inf($it$,$D$.info($it$)+1);\cr
\+(11) &  &     &\ $\}$\cr
\smallskip
\+(12) &  &{\bf forall\_dic\_items}($it,D$) 
cout $<< D$.key($it$) $<<$ ``  " $<<$  $D$.inf($it$) $<<$ ``$\backslash$n";\cr
\smallskip
\+(13) &\ $\}$\cr
\medskip
\centerline{{\bf Program 1:} Counting the number of occurrences of each element of a sequence of strings}


The details are as follows.
In line (1) the dictionary type dictionary(string,int) is defined.
Note that the dictionary module provides dictionaries from $K$
to $I$ where $K$ and $I$ are type variables.
A specific dictionary type is introduced as shown in line (1).
Line (4) introduces $D$ as the name of an object of type
dictionary(string,int); $D$ is initialized to the empty dictionary 
Lines (7) to (11) step through the input sequence. For each string
$s$ we look for an item with key $s$ (line 8). If there is no such item 
in $D$ the lookup operation returns $nil$ and we insert the pair $(s,1)$ 
(line 9). If there is such an item we increase its information (line 10).
Finally, line (12) steps through all items in $D$ and prints the corresponding
key and information values.

The running time of program~1 on a sequence of $n$ strings is $O(n\log n)$,
since the program executes $n$ lookup and at most $n$ insert operations
on $D$ for a cost of $O(\log n)$ each and since the remaining $O(n)$
operations take constant time each. The use of items is not essential
for the asymptotic running time of program~1. Even if a change\_inf
operation would have cost $O(\log n)$, the asymptotic running time
would still be $O(n\log n)$, although with a larger constant factor.
For the next example the use of items is essential.


\bigskip
\bigskip
{\magone Example 2: Priority Queues} 

Priority queues are a variation of dictionaries; they differ in three
aspects from dictionaries: firstly, the set $I$ of informations must
be linearly ordered, secondly, there is an operation findmin() which
returns an item with minimal information, and thirdly, there is a 
restricted change\_inf operation decrease\_inf($it,i$) which decreases
the information stored in item $it$ to $i$. The operation raises an error
if $i$ is larger than the old information stored in item $it$.
Figure~1 shows the specification of the data type priority queue as given
in the LEDA manual ([N90]).

Priority queues are frequently used in network algorithms, e.g., shortest
paths, minimum spanning tree, and maximum flow computations. In these
applications the decrease\_inf operation is typically executed more often
than the other priority queue operations, e.g., in Dijkstra's algorithm
for shortest paths (cf. program~3 in section III) decrease\_inf is
executed $m$ times and the other operations are executed $n$ times.
Here $m$ and $n$ denote the number of edges and vertices of the network
respectively. Note that $m$ can be as large as $n^2$.

Several recent papers, e.g. [FT87] and [AMOT90], have shown that the 
decrease\_inf operation can be realized in time $O(1)$ and all other
operations in time $O(\log n)$. This led to a $O(m+n\log n)$ implementation
of Dijkstra's algorithm. For the constant time implementation of decrease\_inf
it is absolutely crucial that the information to be changed in the data
structure is accessed directly through its position in the data structure
and not through the associated key. A lookup by key would necessarily
have logarithmic cost. In LEDA access by position is achieved by the item
concept in a natural way by simply defining priority queues as collections
of pq\_items and making the first argument of decrease\_inf a pq\_item.

\bigskip
{\bf Remark}: The specification of priority queues given above differs
from the one given in [FT87], [AMOT90] and [CLR90]. There, insert takes
a new item with a predefined contents $(k,i)$ as argument and inserts it
into the queue, i.e., it is the application program's task to create new
items. This either requires the application to know the internal structure
of items, which violates the information hiding principle of abstract data 
types, or it requires an additional operation to create items, which is,
however, not part of the specification given in these papers.
In LEDA the queue itself creates the items. This point of view leads to an
elegant specification which completely separates data type and application
program.

\vfill\eject

\vbox to\vsize{
\hrule
{\bf Priority Queues (priority\_queue)}
\smallskip
An instance $Q$ of the data type $priority\_queue$ 
is a collection of items ($pq\_item$).
Every item contains a key from a type K and an information from a type $I$. 
$K$ is called the key type of $Q$ and $I$ is called the information type of 
$Q$. The number of items in $Q$ is called the size of $Q$. If $Q$ has size 
zero it is called the empty priority queue. We use $<k,i>$ to denote the 
$pq\_item$\ with key $k$ and information $i$. There must exist a linear order
on $I$.
\smallskip
{\bf 1. Declaration of a priority queue type }
\smallskip
\decltwo priority\_queue K I 
\smallskip
introduces a new data type with name \name\ consisting of all
priority queues with key type $K$ and information type $I$.
\smallskip
{\bf 2. Creation of a priority queue}
\smallskip
\create Q {}
\smallskip
creates an instance \var\ of type \name\ and initializes it to the empty queue.
\smallskip
{\bf 3. \operations }
\smallskip
\+\cleartabs & \hskip 1.8truecm & \hskip 6.5truecm &\cr
\+\op K    key {pq\_item\ it}    {returns the key of item $it$.}
\+\nop                           {\precond $it$ is an item in \var.}
\smallskip
\+\op I    inf {pq\_item\ it}    {returns the information of item $it$.}
\+\nop                           {\precond $it$ is an item in \var.}
\smallskip
\+\op pq\_item insert {K\ k,I\ i} {adds a new item $<k,i>$ to \var\ and returns $it$.}
\smallskip
\+\op pq\_item find\_min {}       {returns an item with minimal information}
\+\nop                            {(nil if \var\ is empty)}
\smallskip
\+\op void    del\_item {pq\_item\ it} 
                           {removes the item $it$ from \var.}
\+\nop                     {\precond $it$ is an item in \var.}
\smallskip
\+\op K        del\_min {} 
                           {removes an item with minimal information}
\+\nop                     {from \var\ and returns its key.}
\+\nop                     {\precond \var\ is not empty.}
\smallskip
\+\op pq\_item decrease\_inf {pq\_item\ it,I\ i} 
                           {makes i the new information of item $it$}
\+\nop                     {\precond $it$ is an item in \var\ and $i$}
\+\nop                     {is not larger then $inf(it)$.}
\smallskip
\+\op void clear {}        
                           {makes \var\ the empty priority queue }
\smallskip
\+\op bool empty {} 
                           {returns true, if \var\ is empty, false otherwise}
\smallskip
\+\op int  size  {}
                           {returns the size of \var.}
\smallskip
Priority queues are implemented by Fibonacci Heaps. Operations insert, 
del\_item, del\_min take time $O(\log n)$, find\_min, decrease\_inf, 
key, inf, empty take time $O(1)$ and clear takes time $O(n)$, where $n$ is the 
size of the queue. The space requirement is $O(n)$.
\vfill
\line{\hrulefill\ {\bf Figure 1}: The specification of priority queues.\ \hrulefill}
}

\vfill\eject

\bigskip
{\magone Example 3: Partitions or Disjoint Sets}

In this example we discuss partitions of finite sets, frequently called the 
union-find problem.  An application of partitions is shown in program~4 of 
section~III.  

An object $P$ of type {\sl partition} consists of a finite set
of partition\_items and a partition of this set into blocks.
The declaration $partition$ $P$ introduces $P$ as the name of a
partition and initializes it to the empty partition.
There are three operations.
\medskip
\settabs\+$partition\_item$\quad & $P.union\_blocks(partition\_item\ p,q)$\quad & returns a new partition\_item $it$ and adds the block $\{it\}$ to the partition $P$\cr
\+$partition\_item$& $P.make\_block()$& returns a new partition\_item $it$\cr
\+                 &                  & and adds the block $\{it\}$ to the\cr
\+                 &                  & partition $P$.\cr
\medskip
\+$int$& $P.same\_block(partition\_item\ p,q)$& returns true if $p$ and $q$ belong to\cr
\+	  	   &		      & the same block of the partition $P$.\cr
\medskip
\+$void$& $P.union\_blocks(partition\_item\ p,q)$& unites the blocks of $P$ containing\cr
\+		   &		      & items $p$ and $q$.\cr
\cleartabs
\medskip
We want to stress that the make\_block-operation has no parameter.
It is not given an object which it is supposed to add to the
partition $P$, but the operation itself chooses an item $it$, 
returns it and adds the block $\{it\}$ to the partition $P$.
The user has no idea what $it$ is and he does not need to know.
The only thing, that is important to him, is the partition of
the items into blocks. This usage of items is similar to the usage 
of atoms in SETL.

{\bf Remark}: In the text books ([AHU83], [M84], [T83]) make\_block
takes an item as input and therefore the remark made in the priority
queue example applies here also. We feel that the specification given
above is more natural.

Access by position instead of key is abundant in the design of
efficient data structures; e.g., lists are accessed by position,
all operations in the union-find problem use access by
position, the decrease-inf operation in priority queues is
based on it, and fingers in finger trees are positions.
Thus the position concept is crucial for the design of efficient
data structures. In LEDA we use items as an abstraction of positions.
Many operations take items as arguments or return items as results. 
The examples given above show that the item concept leads to natural 
specifications of data types. More examples can be found in [N90].


\bigskip
\bigskip
{\magonebf III. Graphs}

Graph algorithms are a prime example of combinatorial
computing. LEDA contains several graph types and data types related with
graphs allowing elegant and efficient implementations of graph
and network algorithms. 

$graph$ is the data type of directed graphs.
It provides operations for the updating (inserting and deleting nodes
and edges) and accessing internal informations (number of nodes or edges,
out- and indegree of nodes, endpoints of edges, list of edges adjacent
to a given node, \dots) of directed graphs. Furthermore there are
several iteration statements that can be used to iterate over the
nodes and edges ({\bf for\_all\_nodes}, {\bf for\_all\_edges}, \dots).

Program~2 gives a short demonstration of some graph operations
as they are used to test a directed graph $G$ for acyclicity.
The algorithm uses the data types $graph$ and $node\_set$ whose specifications
are contained in the header file ``LEDA/graph.h'' which is included in line 1.
In line~4 a node set $zero$ for the nodes of graph $G$ is declared. It is
initialized in line~6 with all nodes of indegree 0. In lines 7-15  the
algorithm repeatedly deletes all edges starting in nodes of $zero$ and adds
the new nodes with indegree 0 to $zero$. More precisely, a node $v$ is selected
and deleted from $zero$. Then all edges $e$ starting in $v$ are removed from
$G$. If the removal of edge $e$ decreases the indegree of its target node $w$
to zero, then $w$ is added to $zero$. Finally, $G$ is acyclic if all edges are
removed in the end.
\medskip
\cleartabs
\+(1)\ &\#include $<$LEDA/graph.h$>$\cr
\medskip
\+(2)&bool ACYCLIC($graph\  G$)\cr
\+(3)&$\{$ &// Tests if $G$ is acyclic by repeatedly deleting edges starting in nodes with indegree 0.\cr
\medskip
\+(4)&    &node\_set $zero$;   // Set of all nodes v with indeg(v) = 0\cr
\+(5)&    &node $v,w$;\cr
\medskip
\+(6)&    &{\bf forall\_nodes}($v,G$) \IF ($G$.indeg($v$)==0) $zero$.insert($v$); \cr
\medskip
\+(7)&    &{\bf while} ( !$zero$.empty() )\cr
\+(8)&    &\ \ &$\{$ &$v = zero$.choose();\cr
\+(9)&    &    &     &$zero$.del($v$);\cr
\+(10)&   &    &     &{\bf forall\_adj\_edges}($e,v$)\cr
\+(11)&   &    &     &\ \ &$\{$ &$w$ = $G$.target($e$);\cr
\+(12)&   &    &     &    &     &$G$.del\_edge($e$);\cr
\+(13)&   &    &     &    &     &\IF ($G$.indeg($w$)==0) $zero$.insert($w$);\cr
\+(14)&   &    &     &    &\ $\}$\cr
\+(15)&   &    &\ $\}$\cr
\medskip
\+(16)&   &{\bf return} $G$.number\_of\_edges() == 0;\cr
\+(17)&\ $\}$\cr
\smallskip\noindent
\centerline{{\bf Program 2:} Testing a directed graph for acyclicity.}

Many graph algorithms, especially network algorithms, use additional 
informations associated with the nodes and edges (node labels, edge costs, 
\dots\ ). LEDA provides two ways for associating informations with the nodes
and edges of graphs:

\beginitem
\item {1.}
{{\bf Parameterized Graphs}\nl
A parameterized graph $G$ is a graph whose nodes and edges contain additional
(user defined) informations. Every node contains an element of a data type 
$vtype$, called the node type of $G$ and every edge contains an element of a 
data type $etype$ called the edge type of $G$. All operations defined on 
instances of the data type $graph$ are also defined on instances of any 
parameterized graph type $GRAPH(vtype,etype)$. For parameterized graphs there 
are additional operations to access or update the informations associated 
with its nodes and edges.  
}
\smallskip
\item{}
{Instances of a parameterized graph type can be used wherever an instance 
of the data type $graph$ can be used, e.g., in assignments and as 
arguments to functions with formal parameters of type $graph\&$. 
If a function $f(graph\&\ G)$ is called with an argument $Q$ of type 
$GRAPH(vtype,etype)$ then inside $f$ only the basic graph structure of $Q$
(the adjacency lists) can be accessed. The node and edge informations are 
hidden.  For example, function ACYCLIC accepts instances of any parameterized 
graph type as argument.
}

\item {2.}
{{\bf Node and Edge Arrays}\nl
$node\_array$ and $edge\_array$ are parameterized data types. An instance of the
data type $node\_array(T)$ ($edge\_array(T)$) is an array which is indexed 
by the nodes (edges) of some graph and whose entries are values of type $T$. 
Thus a node (edge) array is a mapping from the nodes (edges) of a graph into a 
set of variables of type $T$.
Node (edge) arrays allow the passing of node and edge informations of networks
to algorithms separatedly from its basic graph structure. In this way reusable
network algorithms accepting instances of arbitrary graph types as arguments
can be designed.
}
\enditem

Examples for reusable network algorithms are the following programs DIJSKTRA 
(single source shortest paths) and MST (minimum spanning tree). We use them to 
illustrate LEDA's comfortable graph type and its interaction with other data 
types.  Program 3 shows Dijkstra's algorithm (cf.~[AHU83], [M84,section~IV.7.2],
[T83]) for the single source shortest path problem in digraphs
with non-negative edge costs. 
\bigskip
\cleartabs
\+(1)\quad &\#include $<$LEDA/graph.h$>$\cr
\+(2)  &\#include $<$LEDA/prio.h$>$\cr
\smallskip
\+(3)  &{\bf declare2}(priority\_queue,node,int)\cr
\+(4)  &{\bf declare}(node\_array,pq\_item)\cr
\smallskip
\+(5)  &void DIJKSTRA(& graph\& $G$, node $s$, edge\_array(int)\& $cost$, \cr
\+(6)  &              & node\_array(int)\& $dist$, node\_array(edge)\& $pred$ ) \cr
\smallskip
\+(7)  &\cleartabs 
        $\{$ & priority\_queue(node,int) $PQ$;\cr
\+(8)  &     & node\_array(pq\_item) $I(G,nil)$;\cr
\+(9)  &     & int $c$;\cr
\+(10) &     & node $u,v$;\cr
\+(11) &     & edge $e$;\cr
\smallskip
\+(12) &     & {\bf forall\_nodes}($v,G$)\cr
\+(13) &     & $\{$ & $ pred[v] = nil$;\cr
\+(14) &     &      & $dist[v] = infinity$;\cr
\+(15) &     &      & $I[v] = PQ$.insert($v,dist[v])$;\cr
\+(16) &     & $\}$\cr
\+(17) &     & $dist[s] = 0$;\cr
\+(18) &     & $PQ$.decrease\_inf($I[s],0)$;\cr
\smallskip
\+(19) &     & \WHILE $(! PQ$.empty())\cr
\+(20) &     & $\{$ &  $u = PQ$.del\_min()\cr
\+(21) &     &      & {\bf forall\_adj\_edges}($e,u$)\cr
\+(22) &     &      & $\{$ &  $v = G.target(e) $;       \cr
\+(23) &     &      &      & $c = dist[u] + cost[e] $;\cr
\+(24) &     &      &      & \IF ( $c < dist[v] $)\cr
\+(25) &     &      &      & $\{$ & $dist[v] = c$;\cr
\+(26) &     &      &      &      & $pred[v] = e$;\cr
\+(27) &     &      &      &      & $PQ$.decrease\_inf($I[v],c$);\cr
\+(28) &     &      &      & \ $\}$\cr
\+(29) &     &      & \ $\}$\cr
\+(30) &     & \ $\}$ // while\cr
\+(31) &\ $\}$\cr
\smallskip
\centerline{{\bf Program 3:} Dijkstra's shortest paths algorithm}

The algorithm uses the data types graph 
and priority queue (lines (1) and (2)).
The input to the algorithm is a graph $G$, a node $s$ of $G$
and a non-negative cost for each edge.
It returns for each node $v$ the length of a shortest path from 
$s$ to $v$ (array $dist$) and the last edge on such a shortest path
(array $pred$).
In LEDA we use edge- and node-arrays for the latter three
parameters. A $node\_array(edge)$ is a mapping from nodes to edges.
The algorithm maintains for each node $v$ a temporary distance
label $dist[v]$.
Initially, $dist[s]=0$ and $dist[v]=\infty$ for $v\ne s$,
cf.~lines (12)--(18).
In LEDA the loop $forall\_nodes(v,G)\{\ldots\}$ can be used to
iterate over all nodes $v$ of a graph $G$.

Dijkstra's algorithm uses a priority queue $PQ$.
The priority queue contains pairs $(v,dist[v])$ and hence has
type $priority\_queue(node,int)$. The type $priority\_queue(node,int)$
is defined in line (3) and in line (7) the queue $PQ$ is created.
Each node $v$ of the graph needs to know the position of the
item $<v,dist[v]>$ in the priority queue.
We therefore declare the data type $node\_array(pq\_item)$ in
line (4) and declare $node\_array(pq\_item)\ I(G,nil)$ in line (8).
In this declaration the parameter $G$ tells LEDA that we want an 
array which is indexed by the nodes of $G$ and the second parameter 
tells it that we want all entries initialized to the $pq\_item$ nil.

Initially, the items $<s,0>$ and $<v,infinity>$ for $v\ne s$
are put into $PQ$, cf.~line (14).
Then in each iteration we select and delete an item $it$ with
minimal $inf$ from $PQ$ and store its key in $u$, cf.~line (20).
We now iterate through all edges $e$ starting in node $u$, cf. line (21).
Let $e=(u,v)$ and let $c=dist[u]+cost[e]$ be the cost of
reaching $v$ through edge $e$, cf.~lines (22) and (23).
If $c$ is smaller than the temporary distance label $dist[v]$
of $v$ then we change $dist[v]$ to $c$ and record $e$ as the
new predecessor of $v$ and decrease the information associated
with $v$ in the priority queue., cf.~lines (24) to (28).

The running time of this algorithm for a graph $G$ with $n$
nodes and $m$ edges is
$O(n+m+T_{declare}+n(T_{insert}+T_{Deletemin}+T_{get\_inf})+m\cdot T_{Decrease\_key})$ where $T_{declare}$ is the cost of declaring
a priority queue and $T_{XYZ}$ is the cost of operation $XYZ$.
With the time bounds stated in section II we obtain an
$O(m+n\log n)$ algorithm.

Program~3 is very similar to the way Dijkstra's algorithm is
presented in textbooks ([AHU83], [M84], [T83]). 
The main difference is that  program~3 is executable code 
whilst the textbooks still require the reader to fill in
(non-trivial) details.

We use the minimum spanning tree problem to further discuss the
interaction between graphs and data types.
Program~4 shows the minimum spanning tree algorithm of Kruskal.
It starts with a spanning forest of $n$ isolated vertices (in line (12)
a partition $P$ is initialized with one block for each vertex of $G$)
and then steps through the edges in order of increasing cost (line (13)
constructs the list $OEL$ of all edges of $G$, line (15) sorts this list
and the forall statement in line (18) iterates over the edges in $OEL$).
When an edge $e$ is considered, it is checked whether the two endpoints
$v$ and $w$ belong to the same tree of the spanning forest (line 21). 
If not, the two trees are united and the edge $e$ is added to the spanning
forest (lines 22 and 23). We refer the reader to [M84, section IV.8] for
the proof of correctness.

\bigskip
\cleartabs
\+(0) \quad&\#include $<$LEDA/graph.h$>$\cr
\+(1) &\#include $<$LEDA/partition.h$>$\cr
\smallskip
\+(2) &{\bf declare}(node\_array,partition\_item);\cr
\smallskip
\+(3) &edge\_array(int) $*C$;\cr
\smallskip
\+(4) &int cmp(edge $e1$, edge $e2$) $\{$ return ($*C[e1] - *C[e2]$); $\}$\cr
\smallskip
\+(5) &void MST(graph\& $G$, edge\_array(int)\& $cost$, edgelist\& $EL$)\cr
\smallskip
\+(6) &// the input is an undirected graph $G$ together with a cost function\cr
\+(7) &// $cost$ on the edges; output: list of edges $EL$ of a minimum spanning tree\cr
\+(8) &$\{$\ & node $v,w$;\cr
\+(9) &  & edge $e$;\cr
\+(10) &  & partition $P$;\cr
\+(11) &  & node\_array(partition\_item) $I(G)$;\cr
\+(12) &  & {\bf forall\_nodes}($v,G$) $I[v] = P$.make\_block();\cr
\smallskip
\+(13) &  & edgelist $OEL = G$.all\_edges();\cr
\+(14) &  & $C = \&cost$;\cr
\+(15) &  & $OEL$.sort($cmp$);\cr
\+(16) &  & // $OEL$ is now the list of edges of $G$ ordered by increasing cost\cr
\smallskip
\+(17) &  & $EL$.clear();\cr
\+(18) &  & {\bf forall}($e,OEL$)\cr
\+(19) &  & $\{$ & $v = G.source(e)$;\cr
\+(20) &  &       & $w = G.target(e)$;\cr
\+(21) &  &       & \IF ($!(P$.same\_block($I[v],I[w]$)))\cr
\+(22) &  &       & $\{$ & $P$.union\_blocks($I[v],I[w]$);\cr
\+(23) &  &       &      & $EL$.append($e$);\cr
\+(24) &  &       &\ $\}$\cr
\+(25) &  &\ $\}$\cr
\+(26) &\ $\}$\cr
\smallskip
\centerline{{\bf Program 4:} Kruskal's minimum spanning tree algorithm}

Programs 3 and 4 show some similarities. 
In both cases a node\_array(item) is used and in both cases the program
starts by creating one item for each node of the graph.
Similar statements occur in many graph algorithms.
A user of LEDA may want to incorporate all of these statements into the 
declaration of the partition or the priority queue.
He can do so (in fact we have done it already) by deriving a data 
type node partition from the data type partition and similarly for 
priority queue. A $node\_partition$ $Q$ consists of a 
$node\_array(partition\_item)\ I$ and a $partition$ $P$.  The declaration 
$node\_partition\ \ Q(G)$ will then execute lines (3), (10), (11), and (12).
The operations on node\_partitions are also easily derived, e.g., 
$Q.same\_block(v,w)$ just calls $P.same\_block(I[v],I[w])$.
For details see section~IV.

\bigskip
\bigskip
{\magonebf IV. Extendibility}

The goal of the LEDA project is the design of a library of reusable data
types and algorithms that can easily be included into user programs.
Of course, such a library can never be complete, i.e., there will
always be situations requiring data types not contained in the library.
Therefore there should be a possibility for users to extend the library by 
adding new data types and algorithms.

LEDA is extendible in two ways:

\beginitem
\item {1.}
{New data types can be added by writing the appropriate \CC modules.
This way of extending the library is suitable for users having
a detailed knowledge of data structures, and with experience in \CC 
programming.
}

\item {2.}
{New data types can also be constructed by combining already existing LEDA
data types. This method allows non-experts to build data types on a higher 
level of description (the level of most example programs in this paper).
An example of such a combination of two LEDA data type is the data type
$node\_partition$ (cf. section~III). It is implemented by combining 
partitions and node\_arrays of partition\_items as follows:
}
\medskip
\cleartabs
\+\hglue\parindent&{\bf class} node\_partition $\{$\cr
\smallskip
\+&// A node\_partition is a partition of the nodes of some graph $G$.\cr
\+&// It consists of a node\_array of partition items and a partition.\cr
\smallskip
\+&node\_array(partition\_item) $I$;\cr
\+&partition $P$;\cr
\smallskip
\+&{\bf public}:\cr
\smallskip
\+&node\_partition($graph\&\ G$)\cr
\+&$\{$\ &// constructs a node\_partition for the nodes of graph $G$\cr
\+&      &node $v$;\cr
\+&      &$I$.init($G,nil$);\cr
\+&      &{\bf forall\_nodes}($v,G$) $I[v] = P$.make\_block();\cr
\+&\ $\}$\cr
\smallskip
\+&\cleartabs 
   void &union\_blocks($node\ v,\ node\ w$) 
                       &$\{$ P.union\_blocks($I[v],I[w]$); $\}$\cr
\+&int  &same\_block($node\ v,\ node\ w$)   
                       &$\{$ {\bf return} $P$.same\_block($I[v],I[w]$); $\}$\cr
\smallskip
\+&$\}$;\cr
\enditem

\bigskip
\bigskip
{\magonebf V. Implementation of LEDA}

This section comments on the implementation of LEDA.
LEDA is written in \CC which is an extension of the C programming language.
In addition to the facilities of C, \CC provides data abstraction, data hiding, object oriented programming, operator overloading and many other features 
suitable for implementing abstract data types. For details of the \CC language 
see [St86] or [Lip89].


Each data type in LEDA is realized by one or more \CC
classes. The operations and operators are member functions of the corresponding
classes.  In \CC a class definition consists of a {\sl declaration part} and an 
{\sl implementation part}. The declaration of a class describes the
interfaces of its member functions (return and parameter types) and the 
private data of each instance of the class. The former part of a class 
declaration corresponds to the abstract specification of the data type.  
The implementation part of a class fills in the \CC code to realize 
the member functions.

\CC does not provide parameterized data types directly. However, [St86]
discusses how the macro facilities of \CC can be used to simulate 
parameterized data types. The parameterized data types of LEDA are
realized by Stroustrup's method.


LEDA provides various kinds of iteration statements, cf. programs 1 to 4.
All iteration statements are implemented by macros which expand the 
iteration into more complicated for-statements.

LEDA can be used under UNIX with the \CC compilers AT\&T cfront 2.0, cfront 2.1,
and GNU \gg (version 1.37). All modules are precompiled and contained
in 3 libraries: basic data types, graph data types and algorithms, and
data types and algorithms for computational geometry. The total size of 
the libraries is about 2 Mbyte.

\bigskip
\bigskip
{\magonebf VI. Summary}

LEDA is a library of efficient data types and algorithms.
At present, its strength is graph algorithms and the data
structures related to them.
The computational geometry part is evolving.

There are several other projects which aim for similar goals as
LEDA, e.g. [B88, So89, Lin89].
We believe, that LEDA compares well with these systems because
of
\smallskip
-- its sizable collection of data types and algorithms\nl
-- the precise and readable specification of these types\nl
-- the item concept for positions and pointers\nl
-- the natural syntax, and\nl
-- the inclusion of many of the most recent and most efficient data structures and algorithms.


\bigskip
{\bf Acknowledgement: } We want to thank our colleagues G. Hotz, J. Loeckx,
W. R\"ulling, K. Sieber and R. Wilhelm for many helpful discussions and our
students D. Basenach, J. Dedorath, E. Haak, M. Muth, M. Wenzel and W. Zimmer
for implementation work.

\bigskip
\bigskip
{\magonebf VII. References}
\bigskip

\parindent 2.5cm 
\ref{AHU83} 
{A.V. Aho, J.E. Hopcroft, J.D. Ullman: ``Data Structures and 
Algorithms'', Addison-Wesley Publishing Company, 1983}
\smallskip
\ref{AMOT90} 
{R.K. Ahuja, K. Mehlhorn, J.B. Orlin, R.E. Tarjan: ``Faster Algorithms
for the Shortest Path Problem'', JACM, Vol. 37, 213-233, 1990}
\smallskip
\ref{B87}
{G. Booch: ``Software Components with Ada'', Benjamin/Cummings Publ. Company, 
1987}
\smallskip
\ref{CLR90}
{T.H. Cormen, C.E. Leiserson, R.L. Rivest: ``Introduction to Algorithms'', 
MIT Press/McGraw-Hill Book Company, 1990 }
\smallskip
\ref{FT87} 
{M.L. Fredman, and R.E. Tarjan: ``Fibonacci Heaps and Their Uses in
Improved Network Optimization Algorithms'', JACM, Vol. 34, 596-615, 1987}
\smallskip
\ref{Lin89} 
{C. Lins: ``The Modula-2 Software Component Library'', Springer 
Publishing Company, 1989}
\smallskip
\ref{Lip89}
{S.B. Lippman: ``\CC Primer'', Addsion-Wesley Publishing Company, 1989} 
\smallskip
\ref{M84} 
{K. Mehlhorn: ``Data Structures and Algorithms'', Vol. 1--3,
Springer Publishing Company, 1984}
\smallskip
\ref{N90}
{S. N\"aher: ``LEDA User Manual Version 2.0'', TR A17/90, Univ. des
Saarlandes, Saarbr\"ucken, 1990}
\smallskip
\ref{So89} 
{J. Soukup: ``Organized C'', Typescript, 1988}
\smallskip 
\ref{St86} 
{B. Stroustrup: `` The \CC Programming Language'', Addison-Wesley 
Publishing Company, 1986}
\smallskip
\ref{T83} 
{R.E. Tarjan: ``Data Structures and Network Algorithms'',
CBMS-NSF Regional Conference Series in Applied Mathematics,
Vol. 44, 1983}
\smallskip

\parindent 0pt

\vfill\eject
\bye
